1. Field of the Invention
The present invention relates to an image encoding method and apparatus, and more particularly to a binary image encoding method for compressing data of binary images for use in data output devices such as a printer, a copier, a facsimile, and so on, a binary image encoding apparatus which implements the method, and a recording medium for executing the method.
2. Description of Related Art
In recent years, the improvements in the resolution and the image quality as well as the ability of processing colored images in the data output devices such as a printer, a copier, a facsimile and so on make the data compression technology (particularly, the compression technology directed to binary image data for preventing a degraded image quality) more and more important in order to reduce the storage capacity and the transmission time. As the compression technology suitable for the binary image data, there have been known the reversible compression techniques such as the arithmetic coding, the Huffman coding, the MH (Modified Huffman) coding, the entropy coding such as the MR (Modified READ (Relative Element Address Designate)) coding, the method which combines these coding techniques with differential coding, and so on. However, these compression techniques encounter the difficulties in realizing the sufficient compression ratio for a pseudo-gray scale binary image which is produced by converting the gradation of a multi-value image in which a natural image is mixed. To compensate for the insufficient compression ratio, conventionally, the binary image is predicted, a data sequence representative of a hit or miss for the prediction is formed into blocks for extending information source, and the blocked data is subjected to the Huffman block encoding. In the following, description will be made on a conventional technique implementing a method of encoding a pseudo-gray scale binary image produced by converting the gradation of a multi-value image in which a natural image is mixed.
FIG. 11 is a block diagram illustrating a conventional binary image encoding apparatus which employs a conventional method of encoding a pseudo-gray scale binary image.
In FIG. 11, reference numeral 1 designates a control unit, 2 a data input unit, 3 a prediction unit, 4 a prediction table, 5 a blocking unit, 6 a Huffman block encoding unit, 7 a Huffman table, and 8 a data output unit.
The following description focuses the operation and so on of the binary image encoding apparatus configured as illustrated.
Referring to FIG. 11, the control unit 1 receives from the data input unit 2 a binary image data which is an input image, and transfers the binary image data to the prediction unit 3. The prediction unit 3 performs the prediction of the received data from information on the surrounding already-encoded pixels using the prediction table 4. The prediction unit 3 converts the received data to a data sequence in which data is equal to xe2x80x9c0xe2x80x9d for a pixel the prediction of which is hit and data is equal to xe2x80x9c1xe2x80x9d for a pixel the prediction of which is miss. Subsequently, the control unit 1 transfers the data sequence indicative of the prediction hit or miss to the blocking unit 5. The blocking unit 5 converts the received data to the blocked data which consists of Mxc3x97N pixels. The Huffman block encoding unit 6 utilizes the Huffman table 7 to perform the Huffman block encoding on the blocked data received from the blocking unit 5 through the control unit 1, and outputs the compressed data resulting from the encoding. The control unit 1 transfers the compressed data from the Huffman block encoding unit 6 to the data output unit 8, and outputs the compressed data from the data output unit 8.
FIGS. 12A and 12B are diagrams for explaining the prediction of the binary image. When the prediction is performed using four reference pixels X1, X2, X3 and X4 shown in FIG. 12A, there are 24=16 possible states for the four pixels, and the prediction function f(X1, X2, X3, X4) is determined for each state in the following manner.
(1) f(X1, X2, X3, X4)=1 for a pattern which has the higher probability that the encoding-target pixel X is equal to xe2x80x9c1xe2x80x9d; and
(2) f(X1, X2, X3, X4)=0 for a pattern which has the higher probability that the encoding-target pixel X is equal to xe2x80x9c0xe2x80x9d.
As shown in FIG. 12B, the prediction function f(X1, X2, X3, X4) is used to predict a binary image to output xe2x80x9c1xe2x80x9d for a prediction-miss pixel and xe2x80x9c0xe2x80x9d for a prediction-hit pixel. The prediction function f(X1, X2, X3, X4) may take the form of a table, as shown by the prediction table 4 in FIG. 11.
FIG. 13 is a diagram for explaining the blocking procedure. As a blocking method, it is contemplated, for example as shown in FIG. 13, that a binary image is blocked into blocks of 4xc3x974 pixels. In this event, since one block consists of 16 pixels, the blocked data is outputted as a 16-bit data sequence.
However, the foregoing conventional binary image encoding method and binary image encoding apparatus, due to the same Huffman block encoding uniformly applied on entire image data, has a problem in that the efficient encoding cannot be accomplished because it cannot sufficiently make use of the feature of image data which presents different correlation between adjacent pixels for each region.
In addition, since the reduction in the redundancy of image data due to the prediction coding is insufficient, there is a problem that it is impossible to perform the efficient encoding.
Thus, a need exists for realizing a higher compression ratio in the conventional binary image encoding method and binary image encoding apparatus, and accordingly a need exists for a recording medium which has recorded thereon this binary image encoding method for execution on a computer.
It is an object of the present invention to provide a binary image encoding method for realizing a higher compression ratio, a binary image encoding apparatus which is capable of realizing a higher compression ratio, and a recording medium having recorded thereon this binary image encoding method for execution on a computer.
In order to solve the problems mentioned above, a binary image encoding method according to the present invention comprises: a predicting step of predicting a binary image; a blocking step of blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether a prediction at the predicting step is hit or miss; and an encoding step of switching a Huffman table in accordance with the blocked data around a Huffman-block-encoding-target block to apply a Huffman block encoding to the Huffman-block-encoding-target block.
Thereby, it is possible to provide a binary image encoding method for realizing the higher compression ratio.
In order to solve the problems mentioned above, a binary image encoding apparatus according to the present invention comprises: a prediction unit for predicting a binary image; a blocking unit for blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether the predictions in the prediction unit are hit or miss; a Huffman block encoding unit for switching a Huffman table in accordance with the blocked data around a Huffman-block-encoding-target block to apply the Huffman block encoding to the target block; and a control unit for controlling the binary image encoding apparatus.
Thereby, it is possible to provide the binary image encoding apparatus for realizing the higher compression ratio.
In order to solve the problems mentioned above, a recording medium according to the present invention has a program recorded thereon, the program causing a computer to execute the steps of: predicting a binary image; blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether a prediction at the predicting step is hit or miss; and switching a Huffman table in accordance with the blocked data around a Huffman-block-encoding-target block to apply a Huffman block encoding to the Huffman-block-encoding-target block.
Thereby, it is possible to provide the recording media for causing a computer to execute the binary image encoding method mentioned above.
In order to solve the problems mentioned above, a binary image encoding apparatus according to the present invention comprises: input means for receiving binary image data; prediction means for predicting a binary image of an encoding-target pixel with reference to a prediction table based on surrounding binary image data around the encoding-target pixel and prediction error data of an already-encoded pixel to produce a data sequence which indicates a prediction hit or miss; a blocking means for blocking the data sequence, which is produced by the prediction means, into blocks; entropy-encoding means for entropy-encoding the blocked data sequence using a table; and output means for outputting entropy-encoded binary compressed data.
Thereby, it is possible to perform the binary image encoding at the higher compression ratio.
The first binary image encoding method according to the present invention comprises: a predicting step of predicting a binary image; a blocking step of blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether a prediction at the predicting step is hit or miss; and an encoding step of switching a Huffman table in accordance with the blocked data around a Huffman-block-encoding-target block to apply a Huffman block encoding to the Huffman-block-encoding-target block.
Due to this construction, it is possible to perform the Huffman block encoding using the optimal Huffman table from the surrounding blocked data. Thereby, the binary image encoding can be advantageously accomplished at the higher compression ratio.
The second binary image encoding method according to the present invention is the first binary image encoding method according to the present invention and further comprises a model determining step of determining an appearance probability distribution model for a value of blocked data of the Huffman-block-encoding-target block with reference to the blocked data, wherein the encoding step includes a step of switching the Huffman table to another Huffman table which is designed optimally to the appearance probability distribution model.
Due to this construction, it is possible to estimate the appearance probability distribution of the value of the blocked data of the Huffman-block-encoding-target block from the surrounding blocked data to perform the Huffman block encoding using the Huffman table designed optimally to the estimated appearance probability distribution. Thereby, the binary image encoding can be advantageously accomplished at the higher compression ratio.
The third binary image encoding method according to the present invention comprises: a predicting step of predicting a binary image; a blocking step of blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether a prediction at the predicting step is hit or miss; a converting step of converting the blocked data to run data when the number of consecutive blocks exceeds a threshold value, all of the predictions of the blocked data for pixels within each of the consecutive blocks being hit, and the run data indicating the number of the consecutive blocks in each of which all of the predictions are hit; and an encoding step of encoding the run data in accordance with a Huffman block encoding scheme when the blocked data is converted to the run data at the converting step, and encoding the blocked data in accordance with the Huffman block encoding scheme when the blocked data is not converted to the run data.
Due to this construction, it is possible to collectively perform the Huffman block encoding on the plurality of blocks as the run data when the plurality of blocks, in each of which all of the predictions are hit, appear in succession. Thereby, the -binary image encoding can be advantageously accomplished at the higher compression ratio.
The fourth binary image encoding method according to the present invention is the third binary image encoding method according to the present invention wherein the converting step includes a step of reducing a maximum run length to a length or less which can be represented by the number of bits equal to the number of pixels constituting one block of the blocked data.
Due to this construction, it is possible to encode the run data using the same Huffman table as that used for the Huffman block encoding performed on the blocked data. Thereby, the binary image encoding can be advantageously accomplished with the extremely simple hardware configuration.
The first binary image encoding apparatus according to the present invention comprises: a prediction unit for predicting a binary image; a blocking unit for blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether the predictions in the prediction unit are hit or miss; a Huffman block encoding unit for switching a Huffman table in accordance with the blocked data around a Huffman-block-encoding-target block to apply the Huffman block encoding to the target block; and a control unit for controlling the binary image encoding apparatus.
Due to this construction, it is possible to perform the Huffman block encoding using the optimal Huffman table selected based on the surrounding blocked data. Thereby, the binary image encoding can be advantageously accomplished at the higher compression ratio.
The second binary image encoding apparatus according to the present invention comprises: a prediction unit for predicting a binary image; a blocking unit for blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether the predictions in the prediction unit are hit or miss; a run data creation unit for converting the blocked data to run data when the number of consecutive blocks exceeds a threshold value, all of the predictions of the blocked data for pixels within each of the consecutive blocks being hit, and the run data indicating the number of the consecutive blocks in each of which all of the predictions are hit; a Huffman block encoding unit for encoding the run data in accordance with a Huffman block encoding scheme when the blocked data is converted to the run data by the run data creation unit, and encoding the blocked data in accordance with the Huffman block encoding scheme when the blocked data is not converted to the run data by the run data creation unit; and a control unit for controlling the binary image encoding apparatus.
Due to this construction, it is possible to collectively perform the Huffman block encoding on the plurality of blocks as the run data when the plurality of blocks, in each of which all of the predictions are hit, appear in succession. Thereby, the binary image encoding can be advantageously accomplished at the higher compression ratio.
The first recording medium according to the present invention has a program recorded thereon, the program causing a computer to execute the steps of: predicting a binary image; blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether a prediction at the predicting step is hit or miss; and switching a Huffman table in accordance with the blocked data around a Huffman-block-encoding-target block to apply a Huffman block encoding to the Huffman-block-encoding-target block.
Due to this construction, it is possible to execute the first binary image encoding method according to the present invention at an arbitrary location at an arbitrary time.
The second recording medium according to the present invention has a program recorded thereon, the program causing a computer to execute the steps of: predicting a binary image; blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether a prediction at the predicting step is hit or miss; determining an appearance probability distribution model for value of blocked data of an encoding-target block with reference to the blocked data; and switching to a Huffman able which is designed optimally to the appearance probability distribution model, to apply the Huffman block encoding to the encoding-target block.
Due to this construction, it is possible to execute the second binary image encoding method according to the present invention at an arbitrary location at an arbitrary time.
The third recording medium according to the present invention has a program recorded thereon, the program causing a computer to execute the steps of: predicting a binary image; blocking a data sequence into blocks to produce blocked data, the data sequence indicating whether a prediction at the predicting step is hit or miss; converting the blocked data to run data when the number of consecutive blocks exceeds a threshold value, all of the predictions of the blocked data for pixels within each of the consecutive blocks being hit, and the run data indicating the number of the consecutive blocks in each of which all of the predictions are hit; and encoding the run data in accordance with a Huffman block encoding scheme when the blocked data is converted to the run data at the converting step, and encoding the blocked data in accordance with the Huffman block encoding scheme when the blocked data is not converted to the run data.
Due to this construction, it is possible to execute the third binary image encoding method according to the present invention at an arbitrary location at an arbitrary time.
The third binary image encoding apparatus according to the present invention comprises: input means for receiving binary image data; prediction means for predicting a binary image of an encoding-target pixel with reference to a prediction table based on surrounding binary image data around the encoding-target pixel and prediction error data of an already-encoded pixel to produce a data sequence which indicates a prediction hit or miss; a blocking means for blocking the data sequence, which is produced by the prediction means, into blocks; entropy-encoding means for entropy-encoding the blocked data sequence using a table; and output means for outputting entropy-encoded binary compressed data.
Thereby, the prediction of the binary image of the encoding-target pixel is performed using the surrounding binary image data and the prediction error data of the already-encoded pixels, so that it is possible to accomplish the binary image encoding at the higher compression ratio.
The fourth binary image encoding apparatus according to the present invention comprises: input means for receiving binary image data; selection means for selecting surrounding binary image data for use in a prediction from a data sequence which indicates a prediction hit or miss in an already-encoded pixel around an encoding-target pixel; prediction means for predicting a binary image of the encoding-target pixel with reference to the selection means and a prediction table to produce a data sequence which indicates a prediction hit or miss; blocking means for blocking the data sequence, which is produced by the prediction means, into blocks; entropy-encoding means for entropy-encoding the blocked data sequence using a table; and output means for outputting entropy-encoded binary compressed data.
Thereby, the prediction of the binary image is performed with the smaller number of the reference pixels by selecting the surrounding pixel for use in the prediction from the prediction error data of the already-encoded pixel, so that it is possible to accomplish the high speed binary image encoding at the higher compression ratio.
The fifth binary image encoding apparatus according to the present invention comprises: input means for receiving binary image data; switching means for switching between a prediction performed with reference to a prediction table and a prediction performed using logical operation means; prediction means for predicting a binary image of an encoding-target pixel with the logical operation means when the prediction is possible through a logical operation, and otherwise with the prediction table, to produce a data sequence which indicates a prediction hit or miss; blocking means for blocking the data sequence, which is produced by the prediction means, into blocks; entropy-encoding means for entropy-encoding the blocked data sequence using a table; and outputting means for outputting entropy-encoded binary compressed data.
Thereby, the prediction is performed through the logical operation by deleting from the prediction table such patterns that need not be described therein for determining the predicted values due to the partiality of the surrounding pixel information, so that it is possible to reduce the size of the prediction table to accomplish the high speed binary image encoding at the higher compression ratio.
The fifth binary image encoding method according to the present invention comprises the steps of: predicting a binary image of an encoding-target pixel with reference to a prediction table based on surrounding binary image data around the encoding-target pixel and prediction error data of an already-encoded pixel to produce a data sequence which indicates a prediction hit or miss; blocking the produced data sequence into blocks; entropy-encoding the blocked data sequence using a table; and outputting entropy-encoded binary compressed data.
Thereby, the prediction of the binary image of the encoding-target pixel is performed using the surrounding binary image data and the prediction error data of the already-encoded pixel, so that the binary image encoding can be accomplished at the higher compression ratio.
The sixth binary image encoding method comprising the steps of: selecting surrounding binary image data for use in a prediction from a data sequence which indicates a prediction hit or miss in an already-encoded pixel around an encoding-target pixel; predicting a binary image of the encoding-target pixel with reference to the selected surrounding binary image data and a prediction table to produce a data sequence which indicates a prediction hit or miss; blocking the produced data sequence into blocks; entropy-encoding the blocked data sequence using a table; and outputting entropy-encoded binary compressed data.
Thereby, the prediction of the binary image using the smaller number of the reference pixels by selecting the surrounding pixel for use in the prediction from the prediction error data of the already-encoded pixel, so that it is possible to accomplish the high speed binary image encoding at the higher compression ratio.
The seventh binary image encoding method according to the present invention comprises the steps of: predicting a binary image of an encoding-target pixel through a logical operation when a prediction is possible through the logical operation, and otherwise with a prediction table, to produce a data sequence which indicates a prediction hit or miss; blocking the produced data sequence into blocks; entropy-encoding the blocked data sequence using a table; and outputting entropy-encoded binary compressed data.
Thereby, the prediction is performed through the logical operation by deleting from the prediction table such patterns that need not be described therein for determining the predicted values due to the partiality of the surrounding pixel information, so that it is possible to reduce the size of the prediction table to accomplish the high speed binary image encoding at the higher compression ratio.
The first information recording medium according to the present invention has a program stored thereon, the program causing a computer to execute the steps of: predicting a binary image of an encoding-target pixel with reference to a prediction table based on surrounding binary image data around the encoding-target pixel and prediction error data of an already-encoded pixel to produce a data sequence which indicates a prediction hit or miss; blocking the produced data sequence into blocks; entropy-encoding the blocked data sequence using a table; and outputting entropy-encoded binary compressed data.
Thereby, the prediction of the binary image of the encoding-target pixel is performed using the surrounding binary image data and the prediction error data of the already-encoded pixel, so that the binary image encoding can be accomplished at the higher compression ratio.
The third information recording medium according to the present invention has a program stored thereon, the program causing a computer to execute the steps of: selecting surrounding binary image data for use in a prediction from a data sequence which indicates a prediction hit or miss in an already-encoded pixel around an encoding-target pixel; predicting a binary image of the encoding-target pixel with reference to the selected surrounding binary image data and a prediction table to produce a data sequence which indicates a prediction hit or miss; blocking the produced data sequence into blocks; entropy-encoding the blocked data sequence using a table; and outputting entropy-encoded binary compressed data.
Thereby, the prediction of the binary image is performed with the smaller number of the reference pixels by selecting the surrounding pixel for use in the prediction from the prediction error data of the already-encoded pixel, so that it is possible to accomplish the high speed binary image encoding at the higher compression ratio.
The third information recording medium having a program stored thereon, the program causing a computer to execute the steps of: predicting a binary image of an encoding-target pixel through a logical operation when a prediction is possible through the logical operation, and otherwise with a prediction table, to produce a data sequence which indicates a prediction hit or miss; blocking the produced data sequence into blocks; entropy-encoding the blocked data sequence using a table; and outputting entropy-encoded binary compressed data.
Thereby, the prediction is performed through the logical operation by deleting from the prediction table such patterns that need not be described therein for determining the predicted values due to the partiality of the surrounding pixel information, so that it is possible to reduce the size of the prediction table to accomplish the high speed binary image encoding at the higher compression ratio.